#lang scheme
;; SICP Chapter 1 exercises solution
;; Author: Zhu, Shenli (zhushenli AT gmail DOT com)
;; Ex.1.3 means exercise 1.3, every exercise solution have source code and some simple test cases (check-expect/check-within).
;; Environment: PLT-scheme(DrScheme)

;;* Exercises status table
;;C : code
;;T : test case
;;A : answer
;;N : not implemented
;;
;;Chapter 1:
;;| No. | Status | No. | Status | No. | Status | No. | Status | No. | Status |
;;|-----+--------+-----+--------+-----+--------+-----+--------+-----+--------|
;;|   1 | N      |   2 | N      |   3 | CT     |   4 | CT     |   5 | CA     |
;;|   6 | CA     |   7 | C      |   8 | CT     |   9 | A      |  10 | CTA    |
;;|  11 | CT     |  12 | CT     |  13 | A      |  14 | A      |  15 | A      |
;;|  16 | CT     |  17 | CT     |  18 | CT     |  19 | ACT    |  20 | ACT    |
;;|  21 | T      |  22 | ACT    |  23 | ACT    |  24 | AT     |  25 | ACT    |
;;|  26 | ACT    |  27 | CT     |  28 | N      |  29 | CT     |  30 | CT     |
;;|  31 | CT     |  32 | CT     |  33 | CT     |  34 | CA     |  35 | T      |
;;|  36 | T      |  37 | CT     |  38 | CT     |  39 | CT     |  40 | CT     |
;;|  41 | CT     |  42 | CT     |  43 | CT     |  44 | CT     |  45 | CT     |
;;|  46 | CT     |     |        |     |        |     |        |     |        |

(require test-engine/scheme-tests)

;; functions exported for other source code
(provide
 gcd
 inc
 square
 identity
 prime?
 )

;;-------------------------------------------------------------------------
;; 1.1 The Elements of Programming
;;-------------------------------------------------------------------------
;; 1.1.6
;; Ex.1.3
(define sum-sqr-l2
  (lambda (x y z)
    (cond
      [(and (>= x z) (>= y z)) (+ (expt x 2) (expt y 2))] ;; smallest z
      [(and (>= x y) (>= z y)) (sum-sqr-l2 x z y)] ;; smallest y
      [(and (>= y x) (>= z x)) (sum-sqr-l2 y z x)]))) ;; smallest x

(check-expect (sum-sqr-l2 1 2 3) 13)
(check-expect (sum-sqr-l2 1 3 2) 13)
(check-expect (sum-sqr-l2 2 1 3) 13)
(check-expect (sum-sqr-l2 2 3 1) 13)
(check-expect (sum-sqr-l2 3 1 2) 13)
(check-expect (sum-sqr-l2 3 2 1) 13)

;; Ex.1.4 a + |b|
(define a-plus-abs-b
  (lambda (a b)
    ((if (> b 0) + -) a b)))

(check-expect (a-plus-abs-b 1 2) 3)
(check-expect (a-plus-abs-b 1 -2) 3)  

;; Ex.1.5 applicative or normal
(define (p) (p))

(define test1
  (lambda (x y)
    (if (= x 0) 0 y)))

;(test1 0 (p))
;; Answer: in applicative-order, p will try to fetch the value it points to and eval it immediately, it will cause a endless loop, while in normal-order, eval of p will be delayed, the result will be 0

;; 1.1.7 Square Root by Newton, copy from book
(define sqrt 
  (lambda (x)
    (sqrt-iter 1.0 x)))

(define sqrt-iter 
  (lambda (guess x)
    ;(if (good-enough? guess x)
    (if (good-enough-frac? guess x)    
        guess
        (sqrt-iter (improve guess x)
                   x))))

(define good-enough? 
  (lambda (guess x)
    (< (abs (- (square guess) x)) 0.001)))

(define square
  (lambda (x) (* x x)))

(define improve 
  (lambda (guess x)
    (average guess (/ x guess))))

(define average 
  (lambda (x y)
    (/ (+ x y) 2)))

;; Ex.1.6, d
(define do-if 
  (lambda (predicate then-clause else-clause)
    (display "do-if-i")
    (cond 
      [predicate then-clause]
      [else else-clause])))

;(define sqrt-iter 
;  (lambda (guess x)
;    (do-if #t ;(good-enough? guess x)
;            guess
;           (sqrt-iter (improve guess x)
;                       x)
;            )))

;(sqrt 1)
(check-within (square (sqrt 100)) 100 0.1) 
(check-within (square (sqrt 8)) 8 0.1) 
(check-within (square (sqrt 0.1)) 0.1 0.001) 
(check-within (square (sqrt 1000000)) 1000000 1) 
;; Ex.1.6 Answer: endless loop. The branch choose else clause forever, why? It's a function argument, so the function do-if will try to bind all the 3 values to its 3 formal arguments, then sqrt-iter will compute a value endlessly.

;; Ex.1.7, good-enough in the book in not good for small numbers, 
(define good-enough-frac? 
  (lambda (guess x)
    (< (/ (abs (- (square guess) x)) x) 0.001)))

;; Ex.1.8, cube-root
(define cube
  (lambda (x)
    (* x x x)))

(define cube-root 
  (lambda (x)
    (cube-root-iter 1.0 x)))

(define cube-root-iter 
  (lambda (guess x)
    ;(if (good-enough? guess x)
    (if (good-enough-cube? guess x)    
        guess
        (cube-root-iter (improve-cube guess x)
                   x))))

(define good-enough-cube? 
  (lambda (guess x)
    (< (/ (abs (- (cube guess) x)) x) 0.001)))

(define improve-cube 
  (lambda (guess x)
    (/ (+ (/ x (square guess)) (* 2 guess)) 3)))


(check-within (cube (cube-root 100)) 100 0.1) 
(check-within (cube (cube-root 8)) 8 0.1) 
(check-within (cube (cube-root 0.1)) 0.1 0.001) 
(check-within (cube (cube-root 1000000)) 1000000 3) 

;;----------------------------------------------------------------------------------
;; 1.2 Procedures and the Processes They Generate
;;----------------------------------------------------------------------------------
;; recursion don't use counter
(define factorial 
  (lambda (n)
    (if (= n 1)
        1
        (* n (factorial (- n 1))))))

(check-expect (factorial 6) 720)

;; iteration use counter
(define factorial-i 
  (lambda(n)
    (fact-iter 1 1 n)))

(define fact-iter 
  (lambda (product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter (* counter product)
                   (+ counter 1)
                   max-count))))

(check-expect (factorial-i 6) 720)

;; Ex.1.9, 1st recursive, 2nd iteration(tail, don't need stack)

;; Ex.1.10
(define A 
  (lambda(x y)
    (cond ((= y 0) 0)
          ((= x 0) (* 2 y))
          ((= y 1) 2)
          (else (A (- x 1)
                   (A x (- y 1)))))))

(check-expect (A 0 5) 10)
(check-expect (A 1 10) 1024)
(check-expect (A 2 4) 65536)
(check-expect (A 3 3) 65536)            
;; Answer: f(n)=2n; g(n)=2^n; h(n)= 2^2^2...^2  

;; recursion
(define fib 
  (lambda (n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib (- n 1))
                   (fib (- n 2)))))))

(check-expect (fib 5) 5)
(check-expect (fib 6) 8)

;; iteration
(define fib-i 
  (lambda (n)
    (fib-iter 1 0 n)))

(define fib-iter 
  (lambda (a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1)))))

(check-expect (fib-i 5) 5)
(check-expect (fib-i 6) 8)

;; Ex.1.11
;; recursion
(define fun1
  (lambda (n)
    (cond
      [(< n 3) n]
      [else (+ (fun1 (- n 1)) 
               (* 2 (fun1 (- n 2))) 
               (* 3 (fun1 (- n 3))))])))
(check-expect (fun1 0) 0 )
(check-expect (fun1 1) 1 )
(check-expect (fun1 2) 2 )
(check-expect (fun1 3) 4 ) 
(check-expect (fun1 4) 11)

;; iteration
(define fun1-i
  (lambda (n)
    (fun1-iter 0 1 2 n)))

(define fun1-iter
  (lambda (fn0 fn1 fn2 count)
    (if (= count 0) fn0
        (fun1-iter fn1 fn2 (+ fn2 (* 2 fn1) (* 3 fn0)) (- count 1)))))
    
(check-expect (fun1-i 0) 0 )
(check-expect (fun1-i 1) 1 )
(check-expect (fun1-i 2) 2 )
(check-expect (fun1-i 3) 4 ) 
(check-expect (fun1-i 4) 11)

;; Ex.1.12
(define pas-tri
  (lambda (l n) ;lth line, nth element, start from 0
    (cond
      [(and (= l 0) (= n 0)) 1]
      [(or (= n 0) (= n l)) (pas-tri 0 0)]
      [else (+ (pas-tri (- l 1) (- n 1)) (pas-tri (- l 1) n))])))
      
(check-expect (pas-tri 0 0) 1)
(check-expect (pas-tri 1 0) 1)
(check-expect (pas-tri 1 1) 1)
(check-expect (pas-tri 2 0) 1)
(check-expect (pas-tri 2 1) 2)
(check-expect (pas-tri 2 2) 1)
(check-expect (pas-tri 3 0) 1)
(check-expect (pas-tri 3 1) 3)
(check-expect (pas-tri 3 2) 3)
(check-expect (pas-tri 3 3) 1)


;; Ex.1.13 Prove: answer: Replace Fib(n+2) and Fib(n+1)+Fib(n), A*B = -1, and prove |B^n/(5^(1/2))| < 1/2, simple 

;; Example: Counting Change
(define count-change 
  (lambda (amount)
    (cc amount 5)))

(define cc 
  (lambda (amount kinds-of-coins)
    (cond ((= amount 0) 1)
          ((or (< amount 0) (= kinds-of-coins 0)) 0)
          (else (+ (cc amount
                       (- kinds-of-coins 1))
                   (cc (- amount
                          (first-denomination kinds-of-coins))
                       kinds-of-coins))))))

(define first-denomination 
  (lambda (kinds-of-coins)
    (cond ((= kinds-of-coins 1) 1)
          ((= kinds-of-coins 2) 5)
          ((= kinds-of-coins 3) 10)
          ((= kinds-of-coins 4) 25)
          ((= kinds-of-coins 5) 50))))

;; Example by footnote(2): 10 cents changed by {10 5 1}
;; [10 {10 5 1}] => [0 {10 5 1}][10 {5 1}]; 
;; [10 {5 1}] => [5 {5 1}][10 {1}]; 
;; [5 {5 1}] => [0 {5 1}][5 {1}]; 
;; ultimately [5 {1}] => [5 {}][4 {1}]
(check-expect (count-change 5) 2)
(check-expect (count-change 10) 4)

;; Ex.1.14
;; space: n (because the smallest coin is penny). step: a^n, because it's a recursive tree, I don't know how to get the more accurate result.

;; Ex.1.15
;; (a) 12.15 / 3^n < 0.1 => n > log3(121.5), so n = 5
;; (b) It's linear recursive, so space = step, space: lna,  

;; Exponentiation
(define expt 
  (lambda (b n)
    (if (= n 0)
        1
        (* b (expt b (- n 1))))))
(check-expect (expt 2 4) 16)

(define expt-i 
  (lambda (b n)
    (expt-iter b n 1)))

(define expt-iter 
  (lambda (b counter product)
    (if (= counter 0)
        product
        (expt-iter b
                   (- counter 1)
                   (* b product)))))
(check-expect (expt-i 2 4) 16)

(define fast-expt 
  (lambda (b n)
    (cond ((= n 0) 1)
          ((even? n) (square (fast-expt b (/ n 2))))
          (else (* b (fast-expt b (- n 1)))))))
(check-expect (fast-expt 2 4) 16)
(check-expect (fast-expt 2 5) 32)  

;; Ex.1.16 iteration (a bit hard, write a simple example to understand)
(define fast-expt-i
  (lambda (b n)
    (fast-expt-iter 1 b n)))

(define fast-expt-iter
  (lambda (a b n)
    (cond
      [(= n 0) a]
      [(= n 1) (* a b)]
      [(even? n) (fast-expt-iter a (square b) (/ n 2))]
      [(odd? n) (fast-expt-iter (* a b) (square b) (/ (- n 1) 2))])))

(check-expect (fast-expt-i 2 1) 2)
(check-expect (fast-expt-i 2 2) 4)
(check-expect (fast-expt-i 2 3) 8)
(check-expect (fast-expt-i 2 4) 16)
(check-expect (fast-expt-i 2 5) 32)  
(check-expect (fast-expt-i 2 6) 64)
(check-expect (fast-expt-i 2 7) 128)  

;; Ex.1.17
(define fast*
  (lambda (a b)
    (cond
      [(= b 1) a]
      [(even? b) (double (fast* a (halve b)))]
      [else (+ (fast* a (- b 1)) a)])))
(define double
  (lambda (b) (* b 2)))
(define halve
  (lambda (b) (/ b 2)))

(check-expect (fast* 5 6) 30)
(check-expect (fast* 6 7) 42)
(check-expect (fast* 19 21) 399)

;; Ex.1.18 iteration
(define fast*-i
  (lambda (a b)
    (fast*-iter 0 a b)))

(define fast*-iter
  (lambda (r a b)
    (cond
      [(= b 0) r]
      [(= b 1) (+ r a)]
      [(even? b) (fast*-iter r (double a) (halve b))]
      [(odd? b) (fast*-iter (+ r a) (double a) (halve (- b 1)))])))

(check-expect (fast*-i 5 6) 30)
(check-expect (fast*-i 6 7) 42)
(check-expect (fast*-i 19 21) 399)

;; Ex.1.19 (too late, go on tomorrow)
;; a'' <- b'q + a'q + a'p
;;     <- b*(q^2 + 2pq) + a*(q^2 + 2pq) + a(p^2 + q^2)
;; so, q' = q^2 + 2pq, p' = (p^2 + q^2)
(define fast-fib 
  (lambda (n)
    (fast-fib-iter 1 0 0 1 n)))

(define fast-fib-iter 
  (lambda (a b p q count)
    (cond ((= count 0) b)
          ((even? count)
           (fast-fib-iter a
                     b
                     (+ (square p) (square q))      ; compute p'
                     (+ (square q) (* 2 p q))      ; compute q'
                     (/ count 2)))
          (else (fast-fib-iter (+ (* b q) (* a q) (* a p))
                          (+ (* b p) (* a q))
                          p
                          q
                          (- count 1))))))

(check-expect (fast-fib 5) 5)
(check-expect (fast-fib 6) 8)

;; GCD: greatest common divisor
;; Ex.1.20
(define gcd 
  (lambda (a b)
    (if (= b 0)
        a
        (gcd b (remainder a b)))))

;(gcd 206 40)

;(check-expect (gcd 206 40) 2)
;; normal-order: will normal-order generate an endless? What's the end of gcd expansion, to remainder? or to even? the question is not very clear?
;; applicative-order
;; give up this question now, and go back when I fully understand normal-order.

;; Searching for divisors
(define smallest-divisor 
  (lambda (n)
    (find-divisor n 2)))

;(define find-divisor 
;  (lambda (n test-divisor)
;    (cond ((> (square test-divisor) n) n)
;          ((divides? test-divisor n) test-divisor)
;          (else (find-divisor n (+ test-divisor 1))))))

(define divides? 
  (lambda (a b)
    (= (remainder b a) 0)))

(define prime? 
  (lambda (n)
    (= n (smallest-divisor n))))

(check-expect (prime? 3) #t)
(check-expect (prime? 4) #f)
(check-expect (prime? 5) #t)
(check-expect (prime? 6) #f)
(check-expect (prime? 7) #t)
(check-expect (prime? 8) #f)
(check-expect (prime? 9) #f)

;; Ex.1.21
(check-expect (smallest-divisor 199) 199)
(check-expect (smallest-divisor 1999) 1999)
(check-expect (smallest-divisor 19999) 7)

;; Ex.1.22
(define search-for-primes
  (lambda (n cnt)
    (cond
      [(= cnt 0) (display"the end\n")]
      [(prime? n) (display n) (newline) (search-for-primes (+ n 1) (- cnt 1))]
      [else (search-for-primes (+ n 1) cnt)])))

;; timed on my computer, the ideal timed ratio between A and B (A/B=10) is sqrt(10)~3
;; Computer in SICP's time is slow, so I enlarge the start number.
;(time (search-for-primes 1000000 10)) ;16
;(time (search-for-primes 10000000 10)) ;31
;(time (search-for-primes 100000000 10)) ;78
;(time (search-for-primes 1000000000 10)) ;250
;(time (search-for-primes 10000000000 10)) ;2844 ? this number is 10 times larger than former one, why?

;; Ex.1.23
(define find-divisor 
  (lambda (n test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor n (next test-divisor ))))))

(define next
  (lambda (n)
    (if (= n 2) 3 (+ n 2))))

(check-expect (prime? 3) #t)
(check-expect (prime? 4) #f)
(check-expect (prime? 5) #t)
(check-expect (prime? 6) #f)
(check-expect (prime? 7) #t)
(check-expect (prime? 8) #f)
(check-expect (prime? 9) #f)

;(time (search-for-primes 1000000 10)) ;0
;(time (search-for-primes 10000000 10)) ;31
;(time (search-for-primes 100000000 10)) ;63
;(time (search-for-primes 1000000000 10)) ;172
;(time (search-for-primes 10000000000 10)) ;1046

;; I don't know why yet.

;; The Fermat test
;; (x*y)%m = ((x%m)*(y%m))%m
(define expmod ;; return (base^exp) % m 
  (lambda (base exp m)
    (cond ((= exp 0) 1)
          ((even? exp)
           (remainder (square (expmod base (/ exp 2) m))
                      m))
          (else
           (remainder (* base (expmod base (- exp 1) m))
                      m)))))

(define fermat-test 
  (lambda (n)
    (define (try-it a)
      (= (expmod a n n) a))
    (try-it (+ 1 (random (- n 1))))))

(define fast-prime? 
  (lambda (n times)
    (cond ((= times 0) true)
          ((fermat-test n) (fast-prime? n (- times 1)))
          (else false))))

(check-expect (fast-prime? 3 10) #t)
(check-expect (fast-prime? 4 10) #f)
(check-expect (fast-prime? 5 10) #t)
(check-expect (fast-prime? 6 10) #f)
(check-expect (fast-prime? 7 10) #t)
(check-expect (fast-prime? 8 10) #f)
(check-expect (fast-prime? 9 10) #f)


(define fast-search-for-primes
  (lambda (n cnt)
    (cond
      [(= cnt 0) (display"the end\n")]
      [(fast-prime? n 100) (display n) (newline) (fast-search-for-primes (+ n 1) (- cnt 1))]
      [else (fast-search-for-primes (+ n 1) cnt)])))

;; Ex.1.24 
;; the time depends on fast-prime?'s times, or other reason? see Ex.1.26
;(time (fast-search-for-primes 1000000 10)) ; 47
;(time (fast-search-for-primes 10000000 10)) ;63
;(time (fast-search-for-primes 100000000 10)) ;141
;(time (fast-search-for-primes 1000000000 10)) ;78
;(time (fast-search-for-primes 10000000000 10)) ;; out of random's boundry, break

;; Ex.1.25, see footnote 3, when base is very large, say (10^6), the multiplication is not feasible
(define expmod2 
  (lambda (base exp m)
    (remainder (fast-expt base exp) m)))

;(time (fast-search-for-primes 1000000 10)) ; endless 

;; Ex.1.26, redundant computation in explicit multiplication, expand the program as a recursive tree, but not a linear recursion
(define expmod3 
  (lambda (base exp m)
    (cond ((= exp 0) 1)
          ((even? exp)
           (remainder (* (expmod base (/ exp 2) m)
                         (expmod base (/ exp 2) m))
                      m))
          (else
           (remainder (* base (expmod base (- exp 1) m))
                      m)))))

;(time (fast-search-for-primes 1000000 10)) ; 

;; Ex.1.27, test all a < n
(define fermat-test-full
  (lambda (n)
    (define try-it 
      (lambda (a)
        (if (= a 1)
           #t
           (and (= (expmod a n n) a) (try-it (- a 1))))))
    (try-it (- n 1))))

(check-expect (fermat-test-full 3) #t)
(check-expect (fermat-test-full 4) #f)
(check-expect (fermat-test-full 5) #t)
(check-expect (fermat-test-full 6) #f)
(check-expect (fermat-test-full 7) #t)
(check-expect (fermat-test-full 8) #f)
(check-expect (fermat-test-full 9) #f)
(check-expect (fermat-test-full 1999) #t)
(check-expect (fermat-test-full 19999) #f)

;; Carmichael numbers
(check-expect (fermat-test-full 561) #t)
(check-expect (fermat-test-full 1105) #t)
(check-expect (fermat-test-full 1729) #t)

;; Ex.1.28 "Miller-Rabin test", don't understand the question very well. In my program, result will always be #f, because 1%n is the success condition, but 1%n is also the fail conditon?
;(define MR-expmod ;; return (base^exp) % m 
;  (lambda (base exp m)
;    (define check_rs
;      (lambda (x)
;        (define rs (lambda (remainder (square x) m)))
;        (if (and (= x 1)) 0 (rs x))))
;    (cond [(= exp 0) 1]
;          [(even? exp)
;           ;; check "nontrivial square root of 1 modulo n", on which step, except first step?
;           ;; (x^2)%n = 1, in which x != 1, (n-1) 
;           ;; must add temp here?
;           (check_rs (MR-expmod base (/ exp 2) m) )]
;          [else
;           (remainder (* base (MR-expmod base (- exp 1) m))
;                      m)])))
;
;(define MR-test 
;  (lambda (n)
;    (define (try-it a)
;      (= (MR-expmod a (- n 1) n) 1))
;    (try-it (+ 1 (random (- n 1))))))
;
;(define MR-fast-prime? 
;  (lambda (n times)
;    (cond ((= times 0) true)
;          ((MR-test n) (MR-fast-prime? n (- times 1)))
;          (else false))))
;
;(check-expect (MR-fast-prime? 3 10) #t)
;(check-expect (MR-fast-prime? 4 10) #f)
;(check-expect (MR-fast-prime? 5 10) #t)
;(check-expect (MR-fast-prime? 6 10) #f)
;(check-expect (MR-fast-prime? 7 10) #t)
;(check-expect (MR-fast-prime? 8 10) #f)
;(check-expect (MR-fast-prime? 9 10) #f)

;;--------------------------------------------------------------------------------
;; 1.3 Formulating Abstractions with Higher-Order Procedures
;;--------------------------------------------------------------------------------
(define sum 
  (lambda (term a next b)
    (if (> a b)
        0
        (+ (term a)
           (sum term (next a) next b)))))

(define (inc n) (+ n 1))
(define (inc2 n) (+ n 2))
(define (identity x) x)

(define (sum-cubes a b)
  (sum cube a inc b))

(check-expect (sum-cubes 1 10) 3025)

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

(check-within (integral cube 0 1 0.01) 0.25 0.01)

;; Ex.1.29 Simpson's Rule
(define do-SR-integral
  (lambda (f a b n)
    (SR-integral f a b n (/ (- b a) n))))

(define SR-integral
  (lambda (f a b n h)
    (define (add-2h x) (+ x (* 2 h)))
    (* (/ h 3)
       (-  
        (+
         (* 2 (sum f a add-2h b))
         (* 4 (sum f (- a h) add-2h (- b h))))
        (+ (f a) (f b))))))
    
(check-within (do-SR-integral cube 0 1 100) 0.25 0.0000001)
                
;; Ex.1.30 iterative sum
(define (sum-i term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (iter a 0))

(define (sum-i-cubes a b)
  (sum-i cube a inc b))

(check-expect (sum-i-cubes 1 10) 3025)
;; Ex.1.31
(define product 
  (lambda (term a next b)
    (if (> a b)
        1
        (* (term a)
           (product term (next a) next b)))))

(define (product-i term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

(define factorial-prod
  (lambda (n)
    (product identity 1 inc n)))

(define factorial-prod-i
  (lambda (n)
    (product-i identity 1 inc n)))

(check-expect (factorial-prod 6) 720)
(check-expect (factorial-prod-i 6) 720)

(define pi-d-4-term
  (lambda (n)
    (/ (* n (+ n 2)) (square (+ n 1)))))

(define pi-d-4
  (lambda (n) ; n must be even here, just for convinience
    (product pi-d-4-term 2 inc2 n)))

(check-within (pi-d-4 100) 0.7853 0.005)

;; Ex.1.32
(define accumulate 
  (lambda (combiner null-value term a next b)
    (if (> a b)
        null-value
        (combiner (term a)
           (accumulate combiner null-value term (next a) next b)))))
     
(define sum-acc
  (lambda (term a next b)
    (accumulate + 0 term a next b)))

(define product-acc
  (lambda (term a next b)
    (accumulate * 1 term a next b)))

(define (sum-acc-cubes a b)
  (sum-acc cube a inc b))

(check-expect (sum-acc-cubes 1 10) 3025)

(define (accumulate-i combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner (term a) result))))
  (iter a null-value))

(define sum-acc-i
  (lambda (term a next b)
    (accumulate-i + 0 term a next b)))

(define (sum-acc-i-cubes a b)
  (sum-acc-i cube a inc b))

(check-expect (sum-acc-i-cubes 1 10) 3025)

;; Ex.1.33 filtered-accumulate
(define filtered-accumulate
  (lambda (filter combiner null-value term a next b)
    (if (> a b)
        null-value
        (combiner (term (if (filter a) a null-value))
           (filtered-accumulate filter combiner null-value term (next a) next b)))))

(define sum-sqr-prime-acc
   (lambda (a b)
     (filtered-accumulate prime? + 0 square a inc b)))

(check-expect (sum-sqr-prime-acc 3 8) 83)

(define product-gcd1-acc
  (lambda (n)
    (define gcd1?
      (lambda (x) (= (gcd n x) 1)))
    (filtered-accumulate gcd1? * 1 identity 2 inc (- n 1))))

(check-expect (product-gcd1-acc 8) 105)

;; Ex.1.34
(define (f g)
  (g 2))
;; (f f)
;; Answer, wrong, (f f) => (f 2) => (2 2), the first element should be a procedure but not a number

;; find root
(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

(define (close-enough? x y)
  (< (abs (- x y)) 0.001))

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of opposite sign" a b)))))

(check-within (half-interval-method sin 2.0 4.0) 3.14 0.01)
(check-within (half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
                                    1.0
                                    2.0) 
              1.89 0.01)

;; find fixed point
(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(check-within (fixed-point cos 1.0) 0.739 0.0010)

;; Ex.1.35
(check-within (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0) 1.618 0.001)

;; Ex.1.36
;; How to add a function call counter? Delay this.
(check-within (fixed-point (lambda (x) (/ (log 1000) (log x))) 2) 4.5555 0.0001)
(check-within (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2) 4.5555 0.0001) 

;; Ex.1.37 "continued fraction"
(define (cont-frac n d k op)
    (define (frac n d k r)
      (if (= r k) 0
          (/ (n r) 
             (op (d r) 
                (frac n d k (+ r 1))))))
    (frac n d k 1))

(define (cont-frac-phi k)
  (cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k +))

(check-within (cont-frac-phi 20) 0.618 0.001)

(define (cont-frac-i n d k)
  (define (frac-i a n d k r)
    (if (= r 0)
        a
        (frac-i (/ (n r) (+ (d r) a)) n d k (- r 1))))
  (frac-i 0 n d k k))  

(define (cont-frac-i-phi k)
  (cont-frac-i (lambda (i) 1.0)
           (lambda (i) 1.0)
           k))

(check-within (cont-frac-i-phi 20) 0.618 0.001)

;; Ex.1.38
(define (cont-frac-euler k)
  (define (D i) 
    (let ((i-r (remainder i 3)))
      (if (= i-r 2)
          (* (/ (+ i 1) 3) 2)
          1)))
  (cont-frac (lambda (i) 1.0)
           D
           k +))

(check-within (cont-frac-euler 100) 0.718 0.001)

;; Ex.1.39
(define (cont-frac-lambert x k)
  (let ((sx (square x)))
    (define (N i)
      (if (= i 1) x sx))
    (define (D i) (- (* 2 i) 1.0))
    (cont-frac N D k -)))

(check-within (cont-frac-lambert 1 100) (tan 1) 0.001)
 
;; 1.3.4 Procedures as Returned Values
(define (average-damp f)
  (lambda (x) (average x (f x))))

(check-expect ((average-damp square) 10) 55)

(define (sqrt-ad x)
  (fixed-point (average-damp (lambda (y) (/ x y)))
               1.0))

(check-within (sqrt-ad 2) 1.414 0.001)

;; Newton's method
(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

;; there is a name contradiction in dx
(define dx 0.00001)

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))  

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (sqrt-n-m x)
  (newtons-method (lambda (y) (- (square y) x))
                  1.0))

(check-within (sqrt-n-m 2) 1.414 0.001)
;; Ex.1.40
(define (cubic a b c)
  (lambda (x) (+ (cube x) (* a (square x)) (* b x) c)))

(check-within (newtons-method (cubic 3 3 1) 1) -1 0.01)

;; Ex.1.41
(define (double-f f)
  (lambda (x) (f (f x))))

(check-expect ((double-f inc) 1) 3)

;; make clear why +16 but not +8?
;; ((df (df df)) f) => ((df df) ((df df) f)), a bit hard to understand
(check-expect ((double-f (double-f inc)) 0) 4)
(check-expect ((double-f (double-f (double-f inc))) 0) 8)
(check-expect (((double-f double-f) inc) 0) 4) ;; 2*2
(check-expect (((double-f (double-f double-f)) inc) 0) 16) ;; 4*4
(check-expect (((double-f (double-f (double-f double-f))) inc) 0) 256) ;; 16*16

;; Ex.1.42
(define (compose f g)
  (lambda(x) (f (g x)))) 

(check-expect ((compose square inc) 6) 49)

;; Ex.1.43
(define (repeated f n)
  (if (= n 1)
      (lambda(x) (f x))
      (compose f (repeated f (- n 1)))))

(check-expect ((repeated square 1) 5) 25)
(check-expect ((repeated square 2) 5) 625)
(check-expect ((repeated square 3) 4) 65536)

;; Ex.1.44 (test with f = x^2)
(define dxs 1)
(define (smooth f)
  (lambda (x) (/ (+ (f (- x dxs)) (f x) (f (+ x dxs))) 3)))

(check-within ((smooth square) 0.0) 0.667 0.001)
(check-within ((smooth square) 1.0) 1.667 0.001)
(check-within ((smooth square) 2.0) 4.667 0.001)

(define (n-fold-smooth f n)
  ((repeated smooth n) f)) 

(check-within ((n-fold-smooth square 2) 1.0) 2.333 0.001)

;; Ex.1.45
(define (cube-root-ad x)
  (fixed-point (average-damp (lambda (y) (/ x (square y))))
               1.0))

(check-within (cube-root-ad 8) 2 0.001)

(define (fourth-root-ad x)
  (fixed-point (average-damp (average-damp (lambda (y) (/ x (cube y)))))
               1.0))

(check-within (fourth-root-ad 16) 2 0.001)

(define (nth-mul n) ;; x^n
  (lambda (x)
    (if (= n 0) 
      1
      (* x ((nth-mul (- n 1)) x)))))

(check-expect ((nth-mul 2) 3) 9)

;; | root | ad |
;; | 2~3  | 1  |
;; | 4~7  | 2  |
;; | 8~15 | 3  |
(define (nth-root-ad x n)
  (fixed-point ((repeated average-damp (inexact->exact (floor (/(log n)(log 2))))) (lambda (y) (/ x ((nth-mul (- n 1)) y)))) 1.0))

(check-within (nth-root-ad (expt 2 2) 2) 2 0.001)
(check-within (nth-root-ad (expt 2 3) 3) 2 0.001)
(check-within (nth-root-ad (expt 2 4) 4) 2 0.001)
(check-within (nth-root-ad (expt 2 5) 5) 2 0.001)
(check-within (nth-root-ad (expt 2 6) 6) 2 0.001)
(check-within (nth-root-ad (expt 2 7) 7) 2 0.001)
(check-within (nth-root-ad (expt 2 8) 8) 2 0.001)
(check-within (nth-root-ad (expt 2 9) 9) 2 0.001)
(check-within (nth-root-ad (expt 2 10) 10) 2 0.001)
(check-within (nth-root-ad (expt 2 11) 11) 2 0.001)
(check-within (nth-root-ad (expt 2 12) 12) 2 0.001)
(check-within (nth-root-ad (expt 2 13) 13) 2 0.001)
(check-within (nth-root-ad (expt 2 14) 14) 2 0.001)
(check-within (nth-root-ad (expt 2 15) 15) 2 0.001)
(check-within (nth-root-ad (expt 2 16) 16) 2 0.001)
(check-within (nth-root-ad (expt 2 17) 17) 2 0.001)
(check-within (nth-root-ad (expt 2 18) 18) 2 0.001)
(check-within (nth-root-ad (expt 2 19) 19) 2 0.001)
(check-within (nth-root-ad (expt 2 20) 20) 2 0.001)

;; Ex.1.46
(define (iterative-improve good-enough? improve-once)
  (define improve
    (lambda (guess) (
               if (good-enough? guess) 
                  guess
                  (improve (improve-once guess)))))
  (lambda (guess) (improve guess)))

;; sqrt by iterative-improve 
(define (sqrt-ii x)
  (define (good-enough? x)
    (lambda (guess) (good-enough-frac? guess x)))
  (define (improve-once x)
    (lambda (guess) (improve guess x)))
  ((iterative-improve (good-enough? x) (improve-once x)) 1.0))

(check-within (sqrt-ii 2) 1.414 0.001)

;; fixed-point by iterative-improve
(define (fixed-point-ii f first-guess)
  (define good-enough?
    (lambda (guess) (= (f guess) guess)))
  (define (improve-once f)
    (lambda (guess) (f guess)))
  ((iterative-improve good-enough? (improve-once f)) first-guess))

(check-within (fixed-point-ii cos 1.0) 0.739 0.001)

;; run all tests
;(test)

